//Given n pairs of parentheses, write a function to generate all combinations 
//of well-formed parentheses. 
//
// 
// Example 1: 
// Input: n = 3
//Output: ["((()))","(()())","(())()","()(())","()()()"]
// Example 2: 
// Input: n = 1
//Output: ["()"]
// 
// 
// Constraints: 
//
// 
// 1 <= n <= 8 
// 
// Related Topics String Dynamic Programming Backtracking 👍 10541 👎 415


package leetcode.editor.en;

import java.util.ArrayList;
import java.util.List;

public class _22_GenerateParentheses {
    public static void main(String[] args) {
        Solution solution = new _22_GenerateParentheses().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public List<String> generateParenthesis(int n) {
            List<String> r = new ArrayList<>();
            dfs(n, n, r, "");
            return r;
        }

        private void dfs(int l, int r, List<String> list, String s) {
            if (l==0 && r==0){
                list.add(s);
                return;
            }
            if(l>r){
                return;
            }

            if (l>0){
                dfs(l-1, r, list, s+"(");
            }
            if (r>0){
                dfs(l, r-1, list, s+")");
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}